import java.util.Arrays;
import java.util.Collections;

public class SortDemo {
    public static void main(String[] args) {
        int num[] = new int[]{9,6,2,5,1,7,3,4,8};
//        bubbleSort(num);   // 冒泡
//        selectSort(num);   // 选择
//        insertSort(num);    // 插入
//        shellSort(num);     // 希尔
//        num = mergeSort(num);    // 归并
//        quickSort(num,0,num.length-1);    // 快排
        heapSort(num);      // 堆排序
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i]+" ");
        }
    }

    private static void heapSort(int[] num) {
    }

    private static void quickSort(int[] num,int low,int high) {
        if(low<high){
            int position = partition(num,low,high);
            quickSort(num,low,position-1);
            quickSort(num,position+1,high);
        }
    }

    private static int partition(int[] num, int low, int high) {
        int pivot = num[high];
        int pointer = low;
        for (int i = low; i < high; i++) {
            if(num[i]<=pivot){
                int temp = num[i];
                num[i] = num[pointer];
                num[pointer] = temp;
                pointer++;
            }
        }
        int temp = num[pointer];
        num[pointer] = num[high];
        num[high] = temp;
        return pointer;
    }

    private static int[] mergeSort(int[] num) {
        if(num.length<=1) return num;
        int len = num.length/2;
        int arr_1[] = Arrays.copyOfRange(num, 0, len); // 左闭右开
        int arr_2[] = Arrays.copyOfRange(num,len,num.length);
        return merge(mergeSort(arr_1),mergeSort(arr_2));
    }

    private static int[] merge(int[] arr_1,int []arr_2) {
        int arr[] = new int[arr_1.length+arr_2.length];
        int idx = 0,idx_1=0,idx_2=0;
        while (idx_1<arr_1.length && idx_2<arr_2.length){
            if(arr_1[idx_1] < arr_2[idx_2]){
                arr[idx] = arr_1[idx_1++];
            }else{
                arr[idx] = arr_2[idx_2++];
            }
            idx++;
        }
        if(idx_1<arr_1.length)
            while (idx_1<arr_1.length){
            arr[idx++] = arr_1[idx_1++];
            }
         if(idx_2<arr_2.length){
            while (idx_2<arr_2.length){
                arr[idx++] = arr_2[idx_2++];
            }
         }
         return arr;
    }

    private static void shellSort(int[] num) {
        int n = num.length;
        int gap = n/2;
        while (gap>0){
            for (int i = gap; i < n; i++) {
                int x = num[i];
                int pre = i-gap;
                while (pre >= 0  && num[pre]>x){
                    num[pre+gap] = num[pre];
                    pre = pre-gap;
                }
                num[pre+gap] = x;
            }
            gap = gap/2;
        }
    }

    private static void insertSort(int[] num) {
        for (int i = 0; i < num.length-1; i++) {
            int inset = i;
            int curr = num[i+1];
            while (inset>=0 && inset < num.length && curr < num[inset]){
                num[inset+1] = num[inset];
                inset--;
            }
            num[inset+1] = curr;
        }
    }

    private static void selectSort(int[] num) {
        for (int i = 0; i < num.length; i++) {
            int x = i;
            for (int j = i+1; j < num.length; j++) {
                if(num[x] > num[j]){
                    x = j;
                }
            }
            if(x!=i){
                int swap = num[x];
                num[x] = num[i];
                num[i] = swap;
            }
        }
    }

    private static void bubbleSort(int[] num) {
        for (int i = 0; i < num.length; i++) {
            for (int j = 0; j < num.length-i-1; j++) {
                if(num[j+1]<num[j]){
                    int temp = num[j+1];
                    num[j+1] = num[j];
                    num[j] = temp;
                }
            }
        }
    }
}
